import java.util.*;

public class Test {
    /*
    题目1：子集
     */
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> lists = new LinkedList<>();

        lists.add(new LinkedList<>());
        int n = nums.length;
        for(int i = 0; i < n; i++){
            int size = lists.size();
            for(int j = 0; j < size; j++){
                List<Integer> list = new LinkedList<>(lists.get(j));
                list.add(nums[i]);
                lists.add(list);
            }
        }
        return lists;
    }

    /*
    题目2：x 的平方根
     */
    public int mySqrt(int x) {
        // 使用二分查找
        if(x < 1){
            return 0;
        }

        long left = 1;
        long right = x;
        while(left < right){
            long mid = left + (right - left + 1) / 2;
            if(mid * mid <= x){
                left = mid;
            }else{
                right = mid - 1;
            }
        }
        return (int)left;

    }

    /*
    题目3：搜索插入的位置
     */
    public int searchInsert(int[] nums, int target) {
        int n = nums.length;

        int left = 0, right = n - 1;
        while(left < right){
            int mid = left + (right - left) / 2;
            if(nums[mid] < target){
                left = mid + 1;
            }else{
                right = mid;
            }
        }
        if(nums[left] < target) return left + 1;
        return left;
    }

    /*
    题目4：山脉数组的峰顶索引
     */
    public int peakIndexInMountainArray(int[] arr) {
        int n = arr.length;

        int left = 0, right = n - 1;
        while(left < right){
            int mid = left + (right - left + 1) / 2;
            if(arr[mid - 1] < arr[mid]){
                left = mid;
            }else{
                right = mid - 1;
            }
        }
        return left;
    }

    /*
    题目5：寻找峰值
     */
    public int findPeakElement(int[] nums) {
        int n = nums.length;

        int left = 0, right = n - 1;

        while(left < right){
            int mid = left + (right - left) / 2;

            if(nums[mid + 1] > nums[mid]){
                left = mid + 1;
            }else{
                right = mid;
            }
        }
        return left;
    }

    /*
    题目6：寻找旋转排序数组中的最小值
     */
    public int findMin(int[] nums) {
        int n = nums.length;

        int left = 0, right = n - 1;
        int tg = nums[right];

        while(left < right){
            int mid = left + (right - left) / 2;
            if(nums[mid] > tg){
                left = mid + 1;
            }else{
                right = mid;
            }
        }
        return nums[left];
    }

    /*
    题目7：0 ~ n - 1 缺失的数字
     */
    public int missingNumber(int[] nums) {
        int n = nums.length;

        int left = 0, right = n - 1;
        while(left < right){
            int mid = left + (right - left) / 2;
            if(nums[mid] == mid){
                left = mid + 1;
            }else{
                right = mid;
            }
        }
        return nums[left] == left ? left + 1 : left;
    }

    /*
    题目8：寻找数组的中心下标
     */
    public int pivotIndex(int[] nums) {
        int n = nums.length;
        int[] f = new int[n];
        int[] g = new int[n];


        for(int i = 1; i < n; i++){
            f[i] = f[i - 1] + nums[i - 1];
        }


        for(int i = n - 2; i >= 0; i--){
            g[i] = g[i + 1] + nums[i + 1];
        }

        for(int i = 0; i < n; i++){
            if(f[i] == g[i]){
                return i;
            }
        }
        return -1;
    }

    /*
    题目9：除自身以外数组的乘积
     */
    public int[] productExceptSelf(int[] nums) {
        int n = nums.length;

        int[] f = new int[n];
        int[] g = new int[n];

        f[0] = 1;
        g[n - 1] = 1;

        for(int i = 1; i < n; i++){
            f[i] = f[i - 1] * nums[i - 1];
        }

        for(int i = n - 2; i >= 0; i--){
            g[i] = g[i + 1] * nums[i + 1];
        }

        for(int i = 0; i < n; i++){
            nums[i] = f[i] * g[i];
        }
        return nums;
    }

    


}
